﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinarySearchTree
{
    struct BinarySearchTree<T> : IEnumerable<T>
        where T : IComparable
    {
        private static int count = 0;
        private static TreeNode<T> root = null;

        public int Count
        {
            get { return count; }
        }

        public bool IsEmpty
        {
            get { return (count == 0); }
        }

        private bool Insert(T newValue, TreeNode<T> currentNode)
        {
            if (currentNode.Value.CompareTo(newValue) > 0)
            {
                if (currentNode.Left == null)
                {
                    currentNode.Left = new TreeNode<T>(newValue, currentNode);
                    count++;
                    return true;
                }
                else
                {
                    return Insert(newValue, currentNode.Left);
                }
            }
            else if (currentNode.Value.CompareTo(newValue) < 0)
            {
                if (currentNode.Right == null)
                {
                    currentNode.Right = new TreeNode<T>(newValue, currentNode);
                    count++;
                    return true;
                }
                else
                {
                    return Insert(newValue, currentNode.Right);
                }
            }
            else
            {
                throw new Exception("This value already exists");
            }
        }

        public bool Insert(T value)
        {
            if (this.IsEmpty == true)
            {
                root = new TreeNode<T>(value);
                count++;
                return true;
            }
            else
            {
                bool isInserted = Insert(value, root);
                return isInserted;
            }
        }

        private TreeNode<T> Search(T value, TreeNode<T> currentNode)
        {
            if (currentNode == null)
            {
                return null;
            }

            if (currentNode.Value.CompareTo(value) > 0)
            {
                return Search(value, currentNode.Left);
            }
            else if (currentNode.Value.CompareTo(value) < 0)
            {
                return Search(value, currentNode.Right);
            }
            else
            {
                return currentNode;
            }
        }

        public bool Contains(T value)
        {
            TreeNode<T> searchedNode = Search(value, root);
            if (searchedNode == null)
            {
                return false;
            }
            else
            {
                return true;
            }
        }

        private TreeNode<T> LeftMostChild(TreeNode<T> currentNode)
        {
            if (currentNode.Left == null)
            {
                return currentNode;
            }
            else
            {
                return LeftMostChild(currentNode.Left);
            }
        }

        private TreeNode<T> RightMostChild(TreeNode<T> currentNode)
        {
            if (currentNode.Right == null)
            {
                return currentNode;
            }
            else
            {
                return RightMostChild(currentNode.Right);
            }
        }

        private void Remove(TreeNode<T> nodeToDel)
        {
            if (nodeToDel.Left == null && nodeToDel.Right == null)
            {
                if (nodeToDel.IsLeft == true)
                {
                    nodeToDel.Parent.Left = null;
                    count--;
                    return;
                }
                else if (nodeToDel.IsRight == true)
                {
                    nodeToDel.Parent.Right = null;
                    count--;
                    return;
                }
                else
                {
                    root = null;
                    count--;
                    return;
                }
            }
            else if (nodeToDel.Left == null)
            {
                if (nodeToDel.IsLeft == true)
                {
                    nodeToDel.Parent.Left = nodeToDel.Right;
                    nodeToDel.Right.Parent = nodeToDel.Parent;
                    count--;
                    return;
                }
                else if (nodeToDel.IsRight == true)
                {
                    nodeToDel.Parent.Right = nodeToDel.Right;
                    nodeToDel.Right.Parent = nodeToDel.Parent;
                    count--;
                    return;
                }
                else
                {
                    root = nodeToDel.Right;
                    root.Parent = null;
                    count--;
                    return;
                }
            }
            else if (nodeToDel.Right == null)
            {
                if (nodeToDel.IsLeft == true)
                {
                    nodeToDel.Parent.Left = nodeToDel.Left;
                    nodeToDel.Left.Parent = nodeToDel.Parent;
                    count--;
                    return;
                }
                else if (nodeToDel.IsRight == true)
                {
                    nodeToDel.Parent.Right = nodeToDel.Left;
                    nodeToDel.Left.Parent = nodeToDel.Parent;
                    count--;
                    return;
                }
                else
                {
                    root = nodeToDel.Left;
                    root.Parent = null;
                    count--;
                    return;
                }
            }
            else
            {
                TreeNode<T> rightMostChildOfLeftSubTree = RightMostChild(nodeToDel.Left);
                nodeToDel.Value = rightMostChildOfLeftSubTree.Value;
                Remove(rightMostChildOfLeftSubTree);
            }
        }

        public void Remove(T value)
        {
            TreeNode<T> nodeToDel = Search(value, root);
            if (nodeToDel == null)
            {
                throw new Exception("You cannot remove nonexistend value");
            }
            else
            {
                Remove(nodeToDel);
            }
        }

        private void Traverse(TreeNode<T> currentNode, List<T> sortedSequence)
        {
            if (currentNode == null)
            {
                return;
            }

            Traverse(currentNode.Left, sortedSequence);
            sortedSequence.Add(currentNode.Value);
            Traverse(currentNode.Right, sortedSequence);
        }

        public IEnumerator<T> GetEnumerator()
        {
            List<T> sortedSequence = new List<T>();
            Traverse(root, sortedSequence);

            for (int i = 0; i < sortedSequence.Count; i++)
            {
                yield return sortedSequence[i];
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public override string ToString()
        {
            StringBuilder tree = new StringBuilder();
            foreach (T item in this)
            {
                tree.Append(item + " ");
            }
            if (tree.Length == 0)
            {
                return "";
            }
            else
            {
                return tree.ToString().Substring(0, tree.Length - 1);
            }
        }
        
        public override bool Equals(object obj)
        {
            try
            {
                BinarySearchTree<T> otherTree = (BinarySearchTree<T>)obj;
                if (count != otherTree.Count)
                {
                    return false;
                }

                List<T> currentTree = new List<T>();
                Traverse(root, currentTree);
                int enumerator = 0;
                foreach (T item in otherTree)
                {
                    if (currentTree[enumerator].Equals(item) == false)
                    {
                        return false;
                    }
                    enumerator++;
                }
                return true;
            }
            catch (InvalidCastException)
            {
                return false;
            }
        }

        public override int GetHashCode()
        {
            int hashCode = 0;
            foreach (T item in this)
            {
                hashCode ^= (item.GetHashCode() << 8);
            }
            return hashCode;
        }
    }
}
